package bintree.LeetCode;
//144. 二叉树的前序遍历
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/*
//递归写法
public class Num144_Solution {

        List<Integer> rep = new ArrayList<>();//这个集合必须要定义在外面，不然每次递归都new一个新的

    public List<Integer> preorderTraversal(TreeNode root) {
        if(root == null){
            return null;
        }
        rep.add(root.val);
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        return rep;
    }

}

 */

//前序遍历的非递归写法——借助栈
public class Num144_Solution {

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> rep = new ArrayList<>();//保存出栈节点的val值
        if(root == null){
            return rep;
        }
        Deque<TreeNode> stack = new LinkedList<>();
        stack.push(root);
        while(!stack.isEmpty()){

            TreeNode cur = stack.pop();//出栈
            rep.add(cur.val);
            //因为是迭代写法，所以需要反过来入栈右左
            //栈是栈顶弹出元素，反过来入左子树才在顶上
            if(cur.right != null){
                stack.push(cur.right);
            }
            if(cur.left != null){
                stack.push(cur.left);
            }

        }
        return rep;
    }
}